Inhibition of the function of CTLA-4, a molecule expressed on activated T cells which down-regulates T cell activity, has resulted in augmented immune reactivity, anti-tumor activity and autoimmunity in animal models. In patients with melanoma, results from early trials suggest that MDX-010, an antibody that inhibits CTLA-4, has clinical anti-tumor activity that correlates with the onset of autoimmune symptoms. A recently completed phase I trial of MDX-010 with a multi-peptide vaccine in patients with resected melanoma at our institution suggested that reversible autoimmunity correlated with prolonged time to relapse and survival and was dose related. In a small phase II trial of MDX-010 with a vaccine in stage IV metatstatic melanoma, three responses were observed in 14 heavily pre-treated patients, all of whom developed autoimmunity. In both trials, autoimmune toxicity was dose limiting. In order to establish whether there is a relationship between tolerable levels of autoimmunity and clinical benefit in melanoma, and to understand the mechanisms of autoimmunity in patients receiving MDX-010, we propose to conduct a phase II study of MDX-010 with a multi-peptide vaccine in patients with resected high-risk melanoma. The trial will be performed in a two-part Simon design but with the achievement of tolerable autoimmune toxicity in at least 50% of patients and the occurrence of no more than 20% dose limiting autoimmune or other toxicity as the desired endpoints. We will address the hypothesis that achieving an acceptable level of autoimmunity that is not dose limiting in a significant proportion of patients with high-risk resected melanoma treated with MDX-010 and a melanoma peptide vaccine will be associated with prolonged time to relapse and overall survival. A translational hypothesis to be tested is whether predicted physiologic effects of the CTLA-4 inhibiting antibody on T cells such as up-regulation of trafficking molecules, skewing of the repertoire against bacterial antigens found in the GI tract, altering of tryptophan metabolism or the presence of genotypic polymorphisms for CTLA-4 can be shown to correlate with the development of autoimmunity and show promise as surrogate markers for clinical benefit. Another translational hypothesis to be evaluated is whether effector-memory T cells that are peptide-specific can be enriched and amplified by an intense regimen of vaccinations over one year followed by booster vaccinations every six months for two years.